排序方式: 共有135条查询结果,搜索用时 125 毫秒
131.
Vaclav Linek 《组合设计杂志》2007,15(5):369-392
A Steiner quadruple system of order v (briefly an SQS(v)) is a pair (X, ) with |X| = v and a set of quadruples taken from X such that every triple in X is in a unique quadruple in . Hanani [Canad J Math 12 (1960), 145–157] showed that an SQS(v) exists if and only if v is {admissible}, that is, v = 0,1 or v ≡ 2,4 (mod 6). Each SQS(v) has a chromatic number when considered as a 4‐uniform hypergraph. Here we show that a 4‐chromatic SQS(v) exists for all admissible v ≥ 20, and that no 4‐chromatic SQS(v) exists for v < 20. Each system we construct admits a proper 4‐coloring that is equitable, that is, any two color classes differ in size by at most one. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 369–392, 2007 相似文献
132.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n
k-1
F(n,m))=O(mn
k
log(n
2
/m)) time and O(n
2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn
3) for weighted graphs, but improves the bound ?(mn
3) to O(n
2
F(n,m))=O(min{mn
8/3,m
3/2
n
2}) for unweighted graphs. The bound ?(mn
4) for k=4 improves the previous best randomized bound ?(n
6) (for m=o(n
2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
Received: April 1999 / Accepted: February 2000?Published online August 18, 2000 相似文献
133.
图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广. 相似文献
134.
135.
Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636). 相似文献